﻿// Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm (find it in Wikipedia).

using System;

class ArrayBinarySearch
{
    static void Main()
    {
        // read Array Size
        uint arraySize;
        do
        {
            Console.Write("Enter sorted array size: ");
        } while (!uint.TryParse(Console.ReadLine(), out arraySize));

        // read array elements
        int[] intArray = new int[arraySize];
        for (int i = 0; i < intArray.Length; i++)
        {
            do
            {
                Console.Write("Enter array elements {0}: ", i + 1);
            } while (!int.TryParse(Console.ReadLine(), out intArray[i]));
        }

        // read searching element
        int searchingElement;
        do
        {
            Console.Write("Enter searching element: ");
        } while (!int.TryParse(Console.ReadLine(), out searchingElement));

        // binary search working only on sorted arrays
        Array.Sort(intArray);

        // binary search
        int start = 0;
        int end = intArray.Length - 1;
        int indexFound = -1;

        while (start <= end)
        {
            int middle = (start + end + 1) / 2;
            int currentElement = intArray[middle];

            if (currentElement == searchingElement)
            {
                indexFound = middle;
                break;
            }
            else if (currentElement < searchingElement)
            {
                start = middle + 1;
            }
            else
            {
                end = middle - 1;
            }
        }

        if (indexFound >= 0)
        {
            Console.WriteLine("Wanted element {0} is found on position {1}", searchingElement, indexFound);
        }
        else
        {
            Console.WriteLine("Wanted element {0} not found", searchingElement);
        }
    }
}